package algorithm.leetcode;

import java.util.LinkedList;
import java.util.List;


/**
 * 圣诞节到了，城堡里有k个小朋友，圣诞老人口袋里带了n件无差别的小礼物，请帮圣诞老人处理：将n个无差别的礼物分给k个小朋友的分法问题
 * 给定n和k，数出分法种数，并枚举所有的分法
 *
 * 仅一行，包含两个参数n(0 <= n <= 10)和k（0<= k<= 10), n 表示礼物的数量，k表示小朋友的数量
 * 输入：3 2
 * 输出：
 * 4
 * ***|
 * **|*
 * *|**
 * |***
 */

public class Huawei {

    public static void main(String[] args) {
        Huawei huawei = new Huawei();
        System.out.println(huawei.get3(5, 2));
    }

    public List<List<Integer>> get2(int n, int k) {
        List<List<Integer>> ans = new LinkedList<>();
        dfs2(ans, new LinkedList<>(), n, k);
        return ans;
    }

    public void dfs2(List<List<Integer>> ans,
                     LinkedList<Integer> curr,
                     int left,
                     int k) {

        if (k == 0) {
            if (left == 0) ans.add(new LinkedList<>(curr));
            return;
        }

        for (int i = 0; i <= left; i++) {
            curr.addLast(i);
            dfs2(ans, curr, left-i, k-1);
            curr.removeLast();
        }

    }


    public List<String> get3(int n, int k) {
        List<String> ans = new LinkedList<>();
        dfs3(ans, new StringBuilder(), n, k-1);
        return ans;
    }

    public void dfs3(List<String> ans,
                     StringBuilder curr,
                     int starLeft,
                     int shuLeft) {

        if (starLeft == 0 && shuLeft == 0) {
            ans.add(curr.toString());
            return;
        }

        if (starLeft >= 1) {
            curr.append("*");
            dfs3(ans, curr, starLeft-1, shuLeft);
            curr.deleteCharAt(curr.length()-1);
        }
        if (shuLeft >= 1) {
            curr.append("|");
            dfs3(ans, curr, starLeft, shuLeft-1);
            curr.deleteCharAt(curr.length()-1);

        }

    }
}
